package leetcode.editor.vip.Solution277;

// 参照labuladong:https://labuladong.github.io/algo/2/21/55/
public class FindTheCelebrity {


    // 请你实现：返回「名人」的编号
    int findCelebrity(int n) {
        // 先假设第一个人是名人
        int cant = 0;
        for (int other = 1; other < n; other++) {
            // 名人认识其他人或者其他人不认识名人，那就不满足名人的条件
            if (knows(cant, other) || !knows(other, cant)) {
                cant = other;
            }else {
                // 名人还是名人
                // other 不可能是名人，排除
                // 什么都不用做，继续假设 cand 是名人
            }
        }
        
        // 现在的 cand 是排除的最后结果，但不能保证一定是名人
        for (int other = 0; other < n; other++) {
            if (other == cant) continue;
            // 需要保证其他人都认识 cand，且 cand 不认识任何其他人
            if (knows(cant, other) || !knows(other, cant)) {
                return -1;
            }
        }

        return cant;
    }

    // 可以直接调用，能够返回 i 是否认识 j
    boolean knows(int i, int j) {
        return false;
    }
}
